/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / Add-Ons / MPW / MPW noweb 2.7 / src / c / recognize.nw

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 20 5c 64 6f 63 75 6d | 65 6e 74 73 74 79 6c 65 |% \docum|entstyle|
|00000010| 5b 6e 6f 77 65 62 5d 7b | 61 72 74 69 63 6c 65 7d |[noweb]{|article}|
|00000020| 0d 25 20 0d 25 20 5c 73 | 65 74 6c 65 6e 67 74 68 |.% .% \s|etlength|
|00000030| 7b 5c 6f 64 64 73 69 64 | 65 6d 61 72 67 69 6e 7d |{\oddsid|emargin}|
|00000040| 7b 30 69 6e 7d 0d 25 20 | 5c 73 65 74 6c 65 6e 67 |{0in}.% |\setleng|
|00000050| 74 68 7b 5c 65 76 65 6e | 73 69 64 65 6d 61 72 67 |th{\even|sidemarg|
|00000060| 69 6e 7d 7b 30 69 6e 7d | 0d 25 20 5c 73 65 74 6c |in}{0in}|.% \setl|
|00000070| 65 6e 67 74 68 7b 5c 74 | 6f 70 6d 61 72 67 69 6e |ength{\t|opmargin|
|00000080| 7d 7b 30 69 6e 7d 0d 25 | 20 5c 61 64 64 74 6f 6c |}{0in}.%| \addtol|
|00000090| 65 6e 67 74 68 7b 5c 74 | 6f 70 6d 61 72 67 69 6e |ength{\t|opmargin|
|000000a0| 7d 7b 2d 5c 68 65 61 64 | 68 65 69 67 68 74 7d 0d |}{-\head|height}.|
|000000b0| 25 20 5c 61 64 64 74 6f | 6c 65 6e 67 74 68 7b 5c |% \addto|length{\|
|000000c0| 74 6f 70 6d 61 72 67 69 | 6e 7d 7b 2d 5c 68 65 61 |topmargi|n}{-\hea|
|000000d0| 64 73 65 70 7d 0d 25 20 | 5c 73 65 74 6c 65 6e 67 |dsep}.% |\setleng|
|000000e0| 74 68 7b 5c 74 65 78 74 | 68 65 69 67 68 74 7d 7b |th{\text|height}{|
|000000f0| 38 2e 39 69 6e 7d 0d 25 | 20 5c 73 65 74 6c 65 6e |8.9in}.%| \setlen|
|00000100| 67 74 68 7b 5c 74 65 78 | 74 77 69 64 74 68 7d 7b |gth{\tex|twidth}{|
|00000110| 36 2e 35 69 6e 7d 0d 25 | 20 5c 73 65 74 6c 65 6e |6.5in}.%| \setlen|
|00000120| 67 74 68 7b 5c 6d 61 72 | 67 69 6e 70 61 72 77 69 |gth{\mar|ginparwi|
|00000130| 64 74 68 7d 7b 30 2e 35 | 69 6e 7d 0d 0d 5c 73 75 |dth}{0.5|in}..\su|
|00000140| 62 73 65 63 74 69 6f 6e | 7b 41 6e 20 45 66 66 69 |bsection|{An Effi|
|00000150| 63 69 65 6e 74 20 53 74 | 72 69 6e 67 20 4d 61 74 |cient St|ring Mat|
|00000160| 63 68 65 72 20 28 62 79 | 20 50 72 65 73 74 6f 6e |cher (by| Preston|
|00000170| 20 42 72 69 67 67 73 29 | 7d 0d 5c 6c 61 62 65 6c | Briggs)|}.\label|
|00000180| 7b 70 72 65 73 74 6f 6e | 7d 0d 0d 5c 73 75 62 73 |{preston|}..\subs|
|00000190| 75 62 73 65 63 74 69 6f | 6e 7b 49 6e 74 72 6f 64 |ubsectio|n{Introd|
|000001a0| 75 63 74 69 6f 6e 7d 0d | 0d 54 68 65 20 6f 62 76 |uction}.|.The obv|
|000001b0| 69 6f 75 73 20 61 70 70 | 72 6f 61 63 68 20 74 6f |ious app|roach to|
|000001c0| 20 74 68 69 73 20 70 72 | 6f 62 6c 65 6d 20 77 6f | this pr|oblem wo|
|000001d0| 75 6c 64 20 62 65 20 71 | 75 69 74 65 20 65 78 70 |uld be q|uite exp|
|000001e0| 65 6e 73 69 76 65 20 66 | 6f 72 0d 6c 61 72 67 65 |ensive f|or.large|
|000001f0| 20 64 6f 63 75 6d 65 6e | 74 73 3b 20 68 6f 77 65 | documen|ts; howe|
|00000200| 76 65 72 2c 20 74 68 65 | 72 65 20 69 73 20 61 6e |ver, the|re is an|
|00000210| 20 69 6e 74 65 72 65 73 | 74 69 6e 67 20 70 61 70 | interes|ting pap|
|00000220| 65 72 20 64 65 73 63 72 | 69 62 69 6e 67 20 61 6e |er descr|ibing an|
|00000230| 0d 65 66 66 69 63 69 65 | 6e 74 20 73 6f 6c 75 74 |.efficie|nt solut|
|00000240| 69 6f 6e 7e 5c 63 69 74 | 65 7b 61 68 6f 3a 65 66 |ion~\cit|e{aho:ef|
|00000250| 66 69 63 69 65 6e 74 7d | 2e 0d 0d 5c 70 61 72 61 |ficient}|...\para|
|00000260| 67 72 61 70 68 7b 42 6f | 69 6c 65 72 70 6c 61 74 |graph{Bo|ilerplat|
|00000270| 65 7d 20 5c 69 6e 64 65 | 6e 74 5c 6e 75 6c 6c 5c |e} \inde|nt\null\|
|00000280| 70 61 72 0d 0d 3c 3c 2a | 3e 3e 3d 0d 3c 3c 49 6e |par..<<*|>>=.<<In|
|00000290| 63 6c 75 64 65 20 66 69 | 6c 65 73 3e 3e 0d 3c 3c |clude fi|les>>.<<|
|000002a0| 68 65 61 64 65 72 3e 3e | 0d 3c 3c 54 79 70 65 20 |header>>|.<<Type |
|000002b0| 64 65 66 69 6e 69 74 69 | 6f 6e 73 3e 3e 0d 3c 3c |definiti|ons>>.<<|
|000002c0| 50 72 6f 74 6f 74 79 70 | 65 73 3e 3e 0d 3c 3c 46 |Prototyp|es>>.<<F|
|000002d0| 75 6e 63 74 69 6f 6e 20 | 64 65 66 69 6e 69 74 69 |unction |definiti|
|000002e0| 6f 6e 73 3e 3e 0d 40 0d | 3c 3c 68 65 61 64 65 72 |ons>>.@.|<<header|
|000002f0| 3e 3e 3d 0d 3c 3c 45 78 | 70 6f 72 74 65 64 20 74 |>>=.<<Ex|ported t|
|00000300| 79 70 65 20 64 65 66 69 | 6e 69 74 69 6f 6e 73 3e |ype defi|nitions>|
|00000310| 3e 0d 3c 3c 45 78 70 6f | 72 74 65 64 20 70 72 6f |>.<<Expo|rted pro|
|00000320| 74 6f 74 79 70 65 73 3e | 3e 0d 40 0d 3c 3c 49 6e |totypes>|>.@.<<In|
|00000330| 63 6c 75 64 65 20 66 69 | 6c 65 73 3e 3e 3d 0d 23 |clude fi|les>>=.#|
|00000340| 69 6e 63 6c 75 64 65 20 | 3c 73 74 72 69 6e 67 2e |include |<string.|
|00000350| 68 3e 0d 40 20 25 64 65 | 66 20 73 74 72 63 68 72 |h>.@ %de|f strchr|
|00000360| 20 73 74 72 63 70 79 20 | 73 74 72 6c 65 6e 0d 3c | strcpy |strlen.<|
|00000370| 3c 49 6e 63 6c 75 64 65 | 20 66 69 6c 65 73 3e 3e |<Include| files>>|
|00000380| 3d 0d 23 69 6e 63 6c 75 | 64 65 20 3c 73 74 64 6c |=.#inclu|de <stdl|
|00000390| 69 62 2e 68 3e 0d 40 20 | 25 64 65 66 20 6d 61 6c |ib.h>.@ |%def mal|
|000003a0| 6c 6f 63 20 63 61 6c 6c | 6f 63 20 66 72 65 65 0d |loc call|oc free.|
|000003b0| 0d 5c 70 61 72 61 67 72 | 61 70 68 7b 45 78 74 65 |.\paragr|aph{Exte|
|000003c0| 72 6e 61 6c 20 49 6e 74 | 65 72 66 61 63 65 7d 0d |rnal Int|erface}.|
|000003d0| 0d 54 68 65 20 65 78 74 | 65 72 6e 61 6c 6c 79 20 |.The ext|ernally |
|000003e0| 76 69 73 69 62 6c 65 20 | 69 6e 74 65 72 66 61 63 |visible |interfac|
|000003f0| 65 20 77 61 73 20 64 65 | 73 69 67 6e 65 64 20 62 |e was de|signed b|
|00000400| 79 20 4e 6f 72 6d 61 6e | 20 52 61 6d 73 65 79 2e |y Norman| Ramsey.|
|00000410| 0d 0d 57 65 20 61 73 73 | 75 6d 65 20 74 68 61 74 |..We ass|ume that|
|00000420| 20 5b 5b 61 6c 70 68 61 | 6e 75 6d 5d 5d 20 61 6e | [[alpha|num]] an|
|00000430| 64 20 5b 5b 73 79 6d 62 | 6f 6c 73 5d 5d 20 70 6f |d [[symb|ols]] po|
|00000440| 69 6e 74 20 74 6f 20 63 | 6f 6e 73 74 61 6e 74 0d |int to c|onstant.|
|00000450| 73 74 72 69 6e 67 73 3b | 20 7b 5c 73 6c 20 69 2e |strings;| {\sl i.|
|00000460| 65 2e 2c 7d 20 77 65 20 | 64 6f 6e 27 74 20 62 6f |e.,} we |don't bo|
|00000470| 74 68 65 72 20 74 6f 20 | 63 6f 70 79 20 74 68 65 |ther to |copy the|
|00000480| 6d 20 69 6e 74 6f 20 73 | 65 70 61 72 61 74 65 6c |m into s|eparatel|
|00000490| 79 0d 61 6c 6c 6f 63 61 | 74 65 64 20 73 70 61 63 |y.alloca|ted spac|
|000004a0| 65 2e 0d 0d 3c 3c 45 78 | 70 6f 72 74 65 64 20 70 |e...<<Ex|ported p|
|000004b0| 72 6f 74 6f 74 79 70 65 | 73 3e 3e 3d 0d 52 65 63 |rototype|s>>=.Rec|
|000004c0| 6f 67 6e 69 7a 65 72 20 | 6e 65 77 5f 72 65 63 6f |ognizer |new_reco|
|000004d0| 67 6e 69 7a 65 72 28 63 | 68 61 72 20 2a 61 6c 70 |gnizer(c|har *alp|
|000004e0| 68 61 6e 75 6d 2c 20 63 | 68 61 72 20 2a 73 79 6d |hanum, c|har *sym|
|000004f0| 62 6f 6c 73 29 3b 0d 40 | 20 25 64 65 66 20 6e 65 |bols);.@| %def ne|
|00000500| 77 5f 72 65 63 6f 67 6e | 69 7a 65 72 0d 3c 3c 45 |w_recogn|izer.<<E|
|00000510| 78 70 6f 72 74 65 64 20 | 74 79 70 65 20 64 65 66 |xported |type def|
|00000520| 69 6e 69 74 69 6f 6e 73 | 3e 3e 3d 0d 74 79 70 65 |initions|>>=.type|
|00000530| 64 65 66 20 73 74 72 75 | 63 74 20 72 65 63 6f 67 |def stru|ct recog|
|00000540| 6e 69 7a 65 72 20 2a 52 | 65 63 6f 67 6e 69 7a 65 |nizer *R|ecognize|
|00000550| 72 3b 0d 40 20 25 64 65 | 66 20 52 65 63 6f 67 6e |r;.@ %de|f Recogn|
|00000560| 69 7a 65 72 0d 41 20 63 | 6f 70 79 20 69 73 20 6d |izer.A c|opy is m|
|00000570| 61 64 65 20 6f 66 20 74 | 68 65 20 73 74 72 69 6e |ade of t|he strin|
|00000580| 67 20 70 6f 69 6e 74 65 | 64 20 74 6f 20 62 79 20 |g pointe|d to by |
|00000590| 5b 5b 69 64 5d 5d 2e 0d | 49 74 20 77 6f 6e 27 74 |[[id]]..|It won't|
|000005a0| 20 68 75 72 74 20 74 6f | 20 61 64 64 20 74 68 65 | hurt to| add the|
|000005b0| 20 73 61 6d 65 20 69 64 | 65 6e 74 69 66 69 65 72 | same id|entifier|
|000005c0| 20 6d 75 6c 74 69 70 6c | 65 20 74 69 6d 65 73 20 | multipl|e times |
|000005d0| 74 6f 20 61 20 67 69 76 | 65 6e 0d 72 65 63 6f 67 |to a giv|en.recog|
|000005e0| 6e 69 7a 65 72 2e 0d 3c | 3c 45 78 70 6f 72 74 65 |nizer..<|<Exporte|
|000005f0| 64 20 70 72 6f 74 6f 74 | 79 70 65 73 3e 3e 3d 0d |d protot|ypes>>=.|
|00000600| 76 6f 69 64 20 61 64 64 | 5f 69 64 65 6e 74 28 52 |void add|_ident(R|
|00000610| 65 63 6f 67 6e 69 7a 65 | 72 20 72 2c 20 63 68 61 |ecognize|r r, cha|
|00000620| 72 20 2a 69 64 29 3b 0d | 76 6f 69 64 20 73 74 6f |r *id);.|void sto|
|00000630| 70 5f 61 64 64 69 6e 67 | 28 52 65 63 6f 67 6e 69 |p_adding|(Recogni|
|00000640| 7a 65 72 20 72 29 3b 0d | 40 20 25 64 65 66 20 61 |zer r);.|@ %def a|
|00000650| 64 64 5f 69 64 65 6e 74 | 20 73 74 6f 70 5f 61 64 |dd_ident| stop_ad|
|00000660| 64 69 6e 67 0d 3c 3c 45 | 78 70 6f 72 74 65 64 20 |ding.<<E|xported |
|00000670| 70 72 6f 74 6f 74 79 70 | 65 73 3e 3e 3d 0d 76 6f |prototyp|es>>=.vo|
|00000680| 69 64 20 73 65 61 72 63 | 68 5f 66 6f 72 5f 69 64 |id searc|h_for_id|
|00000690| 65 6e 74 28 52 65 63 6f | 67 6e 69 7a 65 72 20 72 |ent(Reco|gnizer r|
|000006a0| 2c 20 63 68 61 72 20 2a | 69 6e 70 75 74 2c 20 43 |, char *|input, C|
|000006b0| 61 6c 6c 62 61 63 6b 20 | 66 2c 20 76 6f 69 64 20 |allback |f, void |
|000006c0| 2a 63 6c 6f 73 75 72 65 | 29 3b 0d 40 20 25 64 65 |*closure|);.@ %de|
|000006d0| 66 20 73 65 61 72 63 68 | 5f 66 6f 72 5f 69 64 65 |f search|_for_ide|
|000006e0| 6e 74 0d 0d 5b 5b 69 6e | 73 74 61 6e 63 65 5d 5d |nt..[[in|stance]]|
|000006f0| 20 69 73 20 61 20 70 6f | 69 6e 74 65 72 20 74 6f | is a po|inter to|
|00000700| 20 74 68 65 20 70 6c 61 | 63 65 20 77 69 74 68 69 | the pla|ce withi|
|00000710| 6e 20 5b 5b 69 6e 70 75 | 74 5d 5d 20 74 68 61 74 |n [[inpu|t]] that|
|00000720| 20 77 65 0d 73 61 77 20 | 74 68 65 20 69 64 65 6e | we.saw |the iden|
|00000730| 74 69 66 69 65 72 2e 0d | 3c 3c 45 78 70 6f 72 74 |tifier..|<<Export|
|00000740| 65 64 20 74 79 70 65 20 | 64 65 66 69 6e 69 74 69 |ed type |definiti|
|00000750| 6f 6e 73 3e 3e 3d 0d 74 | 79 70 65 64 65 66 20 76 |ons>>=.t|ypedef v|
|00000760| 6f 69 64 20 28 2a 43 61 | 6c 6c 62 61 63 6b 29 20 |oid (*Ca|llback) |
|00000770| 28 76 6f 69 64 20 2a 63 | 6c 6f 73 75 72 65 2c 20 |(void *c|losure, |
|00000780| 63 68 61 72 20 2a 69 64 | 2c 20 63 68 61 72 20 2a |char *id|, char *|
|00000790| 69 6e 73 74 61 6e 63 65 | 29 3b 0d 40 20 25 64 65 |instance|);.@ %de|
|000007a0| 66 20 43 61 6c 6c 62 61 | 63 6b 0d 40 0d 0d 5c 73 |f Callba|ck.@..\s|
|000007b0| 75 62 73 75 62 73 65 63 | 74 69 6f 6e 7b 44 65 66 |ubsubsec|tion{Def|
|000007c0| 69 6e 69 6e 67 20 74 68 | 65 20 41 75 74 6f 6d 61 |ining th|e Automa|
|000007d0| 74 61 7d 0d 0d 0d 3c 3c | 54 79 70 65 20 64 65 66 |ta}...<<|Type def|
|000007e0| 69 6e 69 74 69 6f 6e 73 | 3e 3e 3d 0d 74 79 70 65 |initions|>>=.type|
|000007f0| 64 65 66 20 73 74 72 75 | 63 74 20 67 6f 74 6f 5f |def stru|ct goto_|
|00000800| 6e 6f 64 65 20 47 6f 74 | 6f 5f 4e 6f 64 65 3b 0d |node Got|o_Node;.|
|00000810| 74 79 70 65 64 65 66 20 | 73 74 72 75 63 74 20 6d |typedef |struct m|
|00000820| 6f 76 65 5f 6e 6f 64 65 | 20 4d 6f 76 65 5f 4e 6f |ove_node| Move_No|
|00000830| 64 65 3b 0d 40 20 25 64 | 65 66 20 47 6f 74 6f 5f |de;.@ %d|ef Goto_|
|00000840| 4e 6f 64 65 20 4d 6f 76 | 65 5f 4e 6f 64 65 0d 3c |Node Mov|e_Node.<|
|00000850| 3c 54 79 70 65 20 64 65 | 66 69 6e 69 74 69 6f 6e |<Type de|finition|
|00000860| 73 3e 3e 3d 0d 74 79 70 | 65 64 65 66 20 73 74 72 |s>>=.typ|edef str|
|00000870| 75 63 74 20 6e 61 6d 65 | 5f 6e 6f 64 65 20 7b 0d |uct name|_node {.|
|00000880| 20 20 73 74 72 75 63 74 | 20 6e 61 6d 65 5f 6e 6f |  struct| name_no|
|00000890| 64 65 20 2a 6e 65 78 74 | 3b 20 2f 2a 20 70 6f 69 |de *next|; /* poi|
|000008a0| 6e 74 73 20 74 6f 20 74 | 68 65 20 6e 65 78 74 20 |nts to t|he next |
|000008b0| 6e 61 6d 65 20 6f 6e 20 | 74 68 65 20 6f 75 74 70 |name on |the outp|
|000008c0| 75 74 20 6c 69 73 74 20 | 2a 2f 0d 20 20 63 68 61 |ut list |*/.  cha|
|000008d0| 72 20 2a 6e 61 6d 65 3b | 0d 7d 20 4e 61 6d 65 5f |r *name;|.} Name_|
|000008e0| 4e 6f 64 65 3b 0d 40 20 | 25 64 65 66 20 4e 61 6d |Node;.@ |%def Nam|
|000008f0| 65 5f 4e 6f 64 65 0d 3c | 3c 54 79 70 65 20 64 65 |e_Node.<|<Type de|
|00000900| 66 69 6e 69 74 69 6f 6e | 73 3e 3e 3d 0d 73 74 72 |finition|s>>=.str|
|00000910| 75 63 74 20 6d 6f 76 65 | 5f 6e 6f 64 65 20 7b 0d |uct move|_node {.|
|00000920| 20 20 4d 6f 76 65 5f 4e | 6f 64 65 20 2a 6e 65 78 |  Move_N|ode *nex|
|00000930| 74 3b 20 20 20 20 20 20 | 2f 2a 20 70 6f 69 6e 74 |t;      |/* point|
|00000940| 73 20 74 6f 20 74 68 65 | 20 6e 65 78 74 20 6e 6f |s to the| next no|
|00000950| 64 65 20 6f 6e 20 74 68 | 65 20 6d 6f 76 65 20 6c |de on th|e move l|
|00000960| 69 73 74 20 2a 2f 0d 20 | 20 47 6f 74 6f 5f 4e 6f |ist */. | Goto_No|
|00000970| 64 65 20 2a 73 74 61 74 | 65 3b 20 20 20 20 20 2f |de *stat|e;     /|
|00000980| 2a 20 74 68 65 20 6e 65 | 78 74 20 73 74 61 74 65 |* the ne|xt state|
|00000990| 20 66 6f 72 20 74 68 69 | 73 20 63 68 61 72 61 63 | for thi|s charac|
|000009a0| 74 65 72 20 2a 2f 0d 20 | 20 63 68 61 72 20 63 3b |ter */. | char c;|
|000009b0| 0d 7d 3b 0d 40 20 25 64 | 65 66 20 6d 6f 76 65 5f |.};.@ %d|ef move_|
|000009c0| 6e 6f 64 65 0d 3c 3c 54 | 79 70 65 20 64 65 66 69 |node.<<T|ype defi|
|000009d0| 6e 69 74 69 6f 6e 73 3e | 3e 3d 0d 73 74 72 75 63 |nitions>|>=.struc|
|000009e0| 74 20 67 6f 74 6f 5f 6e | 6f 64 65 20 7b 0d 20 20 |t goto_n|ode {.  |
|000009f0| 4e 61 6d 65 5f 4e 6f 64 | 65 20 2a 6f 75 74 70 75 |Name_Nod|e *outpu|
|00000a00| 74 3b 20 20 20 20 2f 2a | 20 6c 69 73 74 20 6f 66 |t;    /*| list of|
|00000a10| 20 77 6f 72 64 73 20 65 | 6e 64 69 6e 67 20 69 6e | words e|nding in|
|00000a20| 20 74 68 69 73 20 73 74 | 61 74 65 20 2a 2f 0d 20 | this st|ate */. |
|00000a30| 20 4d 6f 76 65 5f 4e 6f | 64 65 20 2a 6d 6f 76 65 | Move_No|de *move|
|00000a40| 73 3b 20 20 20 20 20 2f | 2a 20 6c 69 73 74 20 6f |s;     /|* list o|
|00000a50| 66 20 70 6f 73 73 69 62 | 6c 65 20 6d 6f 76 65 73 |f possib|le moves|
|00000a60| 20 2a 2f 0d 20 20 47 6f | 74 6f 5f 4e 6f 64 65 20 | */.  Go|to_Node |
|00000a70| 2a 66 61 69 6c 3b 20 20 | 20 20 20 20 2f 2a 20 61 |*fail;  |    /* a|
|00000a80| 6e 64 20 77 68 65 72 65 | 20 74 6f 20 67 6f 20 77 |nd where| to go w|
|00000a90| 68 65 6e 20 6e 6f 20 6d | 6f 76 65 20 66 69 74 73 |hen no m|ove fits|
|00000aa0| 20 2a 2f 0d 20 20 47 6f | 74 6f 5f 4e 6f 64 65 20 | */.  Go|to_Node |
|00000ab0| 2a 6e 65 78 74 3b 20 20 | 20 20 20 20 2f 2a 20 6e |*next;  |    /* n|
|00000ac0| 65 78 74 20 67 6f 74 6f | 20 6e 6f 64 65 20 77 69 |ext goto| node wi|
|00000ad0| 74 68 20 73 61 6d 65 20 | 64 65 70 74 68 20 2a 2f |th same |depth */|
|00000ae0| 0d 7d 3b 0d 40 20 25 64 | 65 66 20 67 6f 74 6f 5f |.};.@ %d|ef goto_|
|00000af0| 6e 6f 64 65 0d 3c 3c 54 | 79 70 65 20 64 65 66 69 |node.<<T|ype defi|
|00000b00| 6e 69 74 69 6f 6e 73 3e | 3e 3d 0d 73 74 72 75 63 |nitions>|>=.struc|
|00000b10| 74 20 72 65 63 6f 67 6e | 69 7a 65 72 20 7b 0d 20 |t recogn|izer {. |
|00000b20| 20 47 6f 74 6f 5f 4e 6f | 64 65 20 2a 72 6f 6f 74 | Goto_No|de *root|
|00000b30| 5b 31 32 38 5d 3b 20 2f | 2a 20 6d 69 67 68 74 20 |[128]; /|* might |
|00000b40| 77 61 6e 74 20 32 35 36 | 2c 20 64 65 70 65 6e 64 |want 256|, depend|
|00000b50| 69 6e 67 20 6f 6e 20 74 | 68 65 20 63 68 61 72 61 |ing on t|he chara|
|00000b60| 63 74 65 72 20 73 65 74 | 20 2a 2f 0d 20 20 63 68 |cter set| */.  ch|
|00000b70| 61 72 20 2a 61 6c 70 68 | 61 73 3b 0d 20 20 63 68 |ar *alph|as;.  ch|
|00000b80| 61 72 20 2a 73 79 6d 73 | 3b 0d 20 20 69 6e 74 20 |ar *syms|;.  int |
|00000b90| 6d 61 78 5f 64 65 70 74 | 68 3b 0d 20 20 47 6f 74 |max_dept|h;.  Got|
|00000ba0| 6f 5f 4e 6f 64 65 20 2a | 2a 64 65 70 74 68 73 3b |o_Node *|*depths;|
|00000bb0| 20 2f 2a 20 61 6e 20 61 | 72 72 61 79 2c 20 6d 61 | /* an a|rray, ma|
|00000bc0| 78 5f 64 65 70 74 68 20 | 6c 6f 6e 67 2c 20 6f 66 |x_depth |long, of|
|00000bd0| 20 6c 69 73 74 73 20 6f | 66 20 67 6f 74 6f 5f 6e | lists o|f goto_n|
|00000be0| 6f 64 65 73 2c 0d 20 20 | 20 20 20 20 20 20 20 20 |odes,.  |        |
|00000bf0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 63 |        |       c|
|00000c00| 72 65 61 74 65 64 20 77 | 68 69 6c 65 20 61 64 64 |reated w|hile add|
|00000c10| 69 6e 67 20 69 64 73 2c | 20 75 73 65 64 20 77 68 |ing ids,| used wh|
|00000c20| 69 6c 65 20 62 75 69 6c | 64 69 6e 67 0d 20 20 20 |ile buil|ding.   |
|00000c30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00000c40| 20 20 20 20 20 20 74 68 | 65 20 66 61 69 6c 75 72 |      th|e failur|
|00000c50| 65 20 66 75 6e 63 74 69 | 6f 6e 73 20 2a 2f 0d 7d |e functi|ons */.}|
|00000c60| 3b 0d 40 20 25 64 65 66 | 20 72 65 63 6f 67 6e 69 |;.@ %def| recogni|
|00000c70| 7a 65 72 20 72 6f 6f 74 | 20 64 65 70 74 68 73 20 |zer root| depths |
|00000c80| 6d 61 78 5f 64 65 70 74 | 68 20 61 6c 70 68 61 73 |max_dept|h alphas|
|00000c90| 20 73 79 6d 73 0d 40 0d | 0d 5c 70 61 72 61 67 72 | syms.@.|.\paragr|
|00000ca0| 61 70 68 7b 41 20 55 74 | 69 6c 69 74 79 20 46 75 |aph{A Ut|ility Fu|
|00000cb0| 6e 63 74 69 6f 6e 7d 0d | 0d 57 65 20 6e 65 65 64 |nction}.|.We need|
|00000cc0| 20 61 20 66 75 6e 63 74 | 69 6f 6e 20 74 68 61 74 | a funct|ion that|
|00000cd0| 2c 20 67 69 76 65 6e 20 | 74 68 65 20 63 75 72 72 |, given |the curr|
|00000ce0| 65 6e 74 20 73 74 61 74 | 65 20 61 6e 64 20 61 20 |ent stat|e and a |
|00000cf0| 63 68 61 72 61 63 74 65 | 72 2c 20 77 69 6c 6c 0d |characte|r, will.|
|00000d00| 72 65 74 75 72 6e 20 74 | 68 65 20 6e 65 78 74 20 |return t|he next |
|00000d10| 73 74 61 74 65 20 61 73 | 20 64 69 72 65 63 74 65 |state as| directe|
|00000d20| 64 20 62 79 20 74 68 65 | 20 60 60 67 6f 74 6f 20 |d by the| ``goto |
|00000d30| 74 61 62 6c 65 2e 27 27 | 20 49 66 20 74 68 65 72 |table.''| If ther|
|00000d40| 65 20 69 73 0d 6e 6f 20 | 64 65 66 69 6e 65 64 20 |e is.no |defined |
|00000d50| 65 6e 74 72 79 20 69 6e | 20 74 68 65 20 74 61 62 |entry in| the tab|
|00000d60| 6c 65 2c 20 74 68 65 20 | 66 75 6e 63 74 69 6f 6e |le, the |function|
|00000d70| 20 72 65 74 75 72 6e 73 | 20 5b 5b 4e 55 4c 4c 5d | returns| [[NULL]|
|00000d80| 5d 2e 0d 3c 3c 46 75 6e | 63 74 69 6f 6e 20 64 65 |]..<<Fun|ction de|
|00000d90| 66 69 6e 69 74 69 6f 6e | 73 3e 3e 3d 0d 73 74 61 |finition|s>>=.sta|
|00000da0| 74 69 63 20 47 6f 74 6f | 5f 4e 6f 64 65 20 2a 67 |tic Goto|_Node *g|
|00000db0| 6f 74 6f 5f 6c 6f 6f 6b | 75 70 28 63 68 61 72 20 |oto_look|up(char |
|00000dc0| 63 2c 20 47 6f 74 6f 5f | 4e 6f 64 65 20 2a 67 29 |c, Goto_|Node *g)|
|00000dd0| 0d 7b 0d 20 20 4d 6f 76 | 65 5f 4e 6f 64 65 20 2a |.{.  Mov|e_Node *|
|00000de0| 6d 20 3d 20 67 2d 3e 6d | 6f 76 65 73 3b 0d 20 20 |m = g->m|oves;.  |
|00000df0| 77 68 69 6c 65 20 28 6d | 20 26 26 20 6d 2d 3e 63 |while (m| && m->c|
|00000e00| 20 21 3d 20 63 29 0d 20 | 20 20 20 6d 20 3d 20 6d | != c). |   m = m|
|00000e10| 2d 3e 6e 65 78 74 3b 0d | 20 20 72 65 74 75 72 6e |->next;.|  return|
|00000e20| 20 6d 20 3f 20 6d 2d 3e | 73 74 61 74 65 20 3a 20 | m ? m->|state : |
|00000e30| 4e 55 4c 4c 3b 0d 7d 0d | 40 20 25 64 65 66 20 67 |NULL;.}.|@ %def g|
|00000e40| 6f 74 6f 5f 6c 6f 6f 6b | 75 70 0d 40 0d 0d 5c 73 |oto_look|up.@..\s|
|00000e50| 75 62 73 75 62 73 65 63 | 74 69 6f 6e 7b 42 75 69 |ubsubsec|tion{Bui|
|00000e60| 6c 64 69 6e 67 20 74 68 | 65 20 41 75 74 6f 6d 61 |lding th|e Automa|
|00000e70| 74 61 7d 0d 0d 54 68 65 | 20 5b 5b 6d 61 78 5f 64 |ta}..The| [[max_d|
|00000e80| 65 70 74 68 5d 5d 20 73 | 68 6f 75 6c 64 20 62 65 |epth]] s|hould be|
|00000e90| 20 69 6e 69 74 69 61 6c | 69 7a 65 64 20 74 6f 20 | initial|ized to |
|00000ea0| 62 65 20 61 74 20 6c 65 | 61 73 74 20 32 2e 0d 3c |be at le|ast 2..<|
|00000eb0| 3c 46 75 6e 63 74 69 6f | 6e 20 64 65 66 69 6e 69 |<Functio|n defini|
|00000ec0| 74 69 6f 6e 73 3e 3e 3d | 0d 52 65 63 6f 67 6e 69 |tions>>=|.Recogni|
|00000ed0| 7a 65 72 20 6e 65 77 5f | 72 65 63 6f 67 6e 69 7a |zer new_|recogniz|
|00000ee0| 65 72 28 63 68 61 72 20 | 2a 61 6c 70 68 61 6e 75 |er(char |*alphanu|
|00000ef0| 6d 2c 20 63 68 61 72 20 | 2a 73 79 6d 62 6f 6c 73 |m, char |*symbols|
|00000f00| 29 0d 7b 0d 20 20 52 65 | 63 6f 67 6e 69 7a 65 72 |).{.  Re|cognizer|
|00000f10| 20 72 20 3d 20 28 52 65 | 63 6f 67 6e 69 7a 65 72 | r = (Re|cognizer|
|00000f20| 29 20 63 61 6c 6c 6f 63 | 28 31 2c 20 73 69 7a 65 |) calloc|(1, size|
|00000f30| 6f 66 28 73 74 72 75 63 | 74 20 72 65 63 6f 67 6e |of(struc|t recogn|
|00000f40| 69 7a 65 72 29 29 3b 0d | 20 20 72 2d 3e 61 6c 70 |izer));.|  r->alp|
|00000f50| 68 61 73 20 3d 20 61 6c | 70 68 61 6e 75 6d 3b 0d |has = al|phanum;.|
|00000f60| 20 20 72 2d 3e 73 79 6d | 73 20 3d 20 73 79 6d 62 |  r->sym|s = symb|
|00000f70| 6f 6c 73 3b 0d 20 20 72 | 2d 3e 6d 61 78 5f 64 65 |ols;.  r|->max_de|
|00000f80| 70 74 68 20 3d 20 31 30 | 3b 0d 20 20 72 2d 3e 64 |pth = 10|;.  r->d|
|00000f90| 65 70 74 68 73 20 3d 20 | 28 47 6f 74 6f 5f 4e 6f |epths = |(Goto_No|
|00000fa0| 64 65 20 2a 2a 29 20 63 | 61 6c 6c 6f 63 28 72 2d |de **) c|alloc(r-|
|00000fb0| 3e 6d 61 78 5f 64 65 70 | 74 68 2c 20 73 69 7a 65 |>max_dep|th, size|
|00000fc0| 6f 66 28 47 6f 74 6f 5f | 4e 6f 64 65 20 2a 29 29 |of(Goto_|Node *))|
|00000fd0| 3b 0d 20 20 72 65 74 75 | 72 6e 20 72 3b 0d 7d 0d |;.  retu|rn r;.}.|
|00000fe0| 40 20 25 64 65 66 20 52 | 65 63 6f 67 6e 69 7a 65 |@ %def R|ecognize|
|00000ff0| 72 0d 40 0d 0d 5c 70 61 | 72 61 67 72 61 70 68 7b |r.@..\pa|ragraph{|
|00001000| 42 75 69 6c 64 69 6e 67 | 20 74 68 65 20 47 6f 74 |Building| the Got|
|00001010| 6f 20 54 61 62 6c 65 7d | 0d 0d 57 65 20 61 73 73 |o Table}|..We ass|
|00001020| 75 6d 65 20 5b 5b 69 64 | 5d 5d 20 69 73 20 61 74 |ume [[id|]] is at|
|00001030| 20 6c 65 61 73 74 20 31 | 20 63 68 61 72 61 63 74 | least 1| charact|
|00001040| 65 72 20 6c 6f 6e 67 2e | 0d 3c 3c 46 75 6e 63 74 |er long.|.<<Funct|
|00001050| 69 6f 6e 20 64 65 66 69 | 6e 69 74 69 6f 6e 73 3e |ion defi|nitions>|
|00001060| 3e 3d 0d 76 6f 69 64 20 | 61 64 64 5f 69 64 65 6e |>=.void |add_iden|
|00001070| 74 28 52 65 63 6f 67 6e | 69 7a 65 72 20 72 2c 20 |t(Recogn|izer r, |
|00001080| 63 68 61 72 20 2a 69 64 | 29 0d 7b 0d 20 20 69 6e |char *id|).{.  in|
|00001090| 74 20 64 65 70 74 68 20 | 3d 20 32 3b 0d 20 20 63 |t depth |= 2;.  c|
|000010a0| 68 61 72 20 2a 70 20 3d | 20 69 64 3b 0d 20 20 63 |har *p =| id;.  c|
|000010b0| 68 61 72 20 63 20 3d 20 | 2a 70 2b 2b 3b 0d 20 20 |har c = |*p++;.  |
|000010c0| 47 6f 74 6f 5f 4e 6f 64 | 65 20 2a 71 20 3d 20 72 |Goto_Nod|e *q = r|
|000010d0| 2d 3e 72 6f 6f 74 5b 63 | 5d 3b 0d 20 20 69 66 20 |->root[c|];.  if |
|000010e0| 28 21 71 29 20 0d 20 20 | 20 20 3c 3c 43 72 65 61 |(!q) .  |  <<Crea|
|000010f0| 74 65 20 61 6e 20 65 6e | 74 72 79 20 66 6f 72 20 |te an en|try for |
|00001100| 5b 5b 72 6f 6f 74 5b 63 | 5d 5d 5d 3e 3e 0d 20 20 |[[root[c|]]]>>.  |
|00001110| 63 20 3d 20 2a 70 2b 2b | 3b 0d 20 20 77 68 69 6c |c = *p++|;.  whil|
|00001120| 65 20 28 63 29 20 7b 0d | 20 20 20 20 47 6f 74 6f |e (c) {.|    Goto|
|00001130| 5f 4e 6f 64 65 20 2a 6e | 65 77 20 3d 20 67 6f 74 |_Node *n|ew = got|
|00001140| 6f 5f 6c 6f 6f 6b 75 70 | 28 63 2c 20 71 29 3b 0d |o_lookup|(c, q);.|
|00001150| 20 20 20 20 69 66 20 28 | 21 6e 65 77 29 0d 20 20 |    if (|!new).  |
|00001160| 20 20 20 20 3c 3c 43 72 | 65 61 74 65 20 61 20 6e |    <<Cr|eate a n|
|00001170| 65 77 20 67 6f 74 6f 20 | 65 6e 74 72 79 20 61 6e |ew goto |entry an|
|00001180| 64 20 61 74 74 61 63 68 | 20 74 6f 20 5b 5b 71 5d |d attach| to [[q]|
|00001190| 5d 27 73 20 6d 6f 76 65 | 20 6c 69 73 74 3e 3e 0d |]'s move| list>>.|
|000011a0| 20 20 20 20 71 20 3d 20 | 6e 65 77 3b 0d 20 20 20 |    q = |new;.   |
|000011b0| 20 64 65 70 74 68 2b 2b | 3b 0d 20 20 20 20 63 20 | depth++|;.    c |
|000011c0| 3d 20 2a 70 2b 2b 3b 0d | 20 20 7d 0d 20 20 3c 3c |= *p++;.|  }.  <<|
|000011d0| 53 65 74 20 5b 5b 71 2d | 3e 6f 75 74 70 75 74 5d |Set [[q-|>output]|
|000011e0| 5d 20 74 6f 20 5b 5b 69 | 64 5d 5d 20 28 69 66 20 |] to [[i|d]] (if |
|000011f0| 6e 6f 74 20 61 6c 72 65 | 61 64 79 20 70 72 65 73 |not alre|ady pres|
|00001200| 65 6e 74 29 3e 3e 0d 7d | 0d 40 20 25 64 65 66 20 |ent)>>.}|.@ %def |
|00001210| 61 64 64 5f 69 64 65 6e | 74 0d 3c 3c 43 72 65 61 |add_iden|t.<<Crea|
|00001220| 74 65 20 61 6e 20 65 6e | 74 72 79 20 66 6f 72 20 |te an en|try for |
|00001230| 5b 5b 72 6f 6f 74 5b 63 | 5d 5d 5d 3e 3e 3d 0d 7b |[[root[c|]]]>>=.{|
|00001240| 0d 20 20 71 20 3d 20 28 | 47 6f 74 6f 5f 4e 6f 64 |.  q = (|Goto_Nod|
|00001250| 65 20 2a 29 20 63 61 6c | 6c 6f 63 28 31 2c 20 73 |e *) cal|loc(1, s|
|00001260| 69 7a 65 6f 66 28 47 6f | 74 6f 5f 4e 6f 64 65 29 |izeof(Go|to_Node)|
|00001270| 29 3b 0d 20 20 72 2d 3e | 72 6f 6f 74 5b 63 5d 20 |);.  r->|root[c] |
|00001280| 3d 20 71 3b 0d 20 20 71 | 2d 3e 6e 65 78 74 20 3d |= q;.  q|->next =|
|00001290| 20 72 2d 3e 64 65 70 74 | 68 73 5b 31 5d 3b 0d 20 | r->dept|hs[1];. |
|000012a0| 20 72 2d 3e 64 65 70 74 | 68 73 5b 31 5d 20 3d 20 | r->dept|hs[1] = |
|000012b0| 71 3b 0d 7d 0d 3c 3c 43 | 72 65 61 74 65 20 61 20 |q;.}.<<C|reate a |
|000012c0| 6e 65 77 20 67 6f 74 6f | 20 65 6e 74 72 79 20 61 |new goto| entry a|
|000012d0| 6e 64 20 61 74 74 61 63 | 68 20 74 6f 20 5b 5b 71 |nd attac|h to [[q|
|000012e0| 5d 5d 27 73 20 6d 6f 76 | 65 20 6c 69 73 74 3e 3e |]]'s mov|e list>>|
|000012f0| 3d 0d 7b 0d 20 20 4d 6f | 76 65 5f 4e 6f 64 65 20 |=.{.  Mo|ve_Node |
|00001300| 2a 6e 65 77 5f 6d 6f 76 | 65 20 3d 20 28 4d 6f 76 |*new_mov|e = (Mov|
|00001310| 65 5f 4e 6f 64 65 20 2a | 29 20 6d 61 6c 6c 6f 63 |e_Node *|) malloc|
|00001320| 28 73 69 7a 65 6f 66 28 | 4d 6f 76 65 5f 4e 6f 64 |(sizeof(|Move_Nod|
|00001330| 65 29 29 3b 0d 20 20 6e | 65 77 20 3d 20 28 47 6f |e));.  n|ew = (Go|
|00001340| 74 6f 5f 4e 6f 64 65 20 | 2a 29 20 63 61 6c 6c 6f |to_Node |*) callo|
|00001350| 63 28 31 2c 20 73 69 7a | 65 6f 66 28 47 6f 74 6f |c(1, siz|eof(Goto|
|00001360| 5f 4e 6f 64 65 29 29 3b | 0d 20 20 6e 65 77 5f 6d |_Node));|.  new_m|
|00001370| 6f 76 65 2d 3e 73 74 61 | 74 65 20 3d 20 6e 65 77 |ove->sta|te = new|
|00001380| 3b 0d 20 20 6e 65 77 5f | 6d 6f 76 65 2d 3e 63 20 |;.  new_|move->c |
|00001390| 3d 20 63 3b 0d 20 20 6e | 65 77 5f 6d 6f 76 65 2d |= c;.  n|ew_move-|
|000013a0| 3e 6e 65 78 74 20 3d 20 | 71 2d 3e 6d 6f 76 65 73 |>next = |q->moves|
|000013b0| 3b 0d 20 20 71 2d 3e 6d | 6f 76 65 73 20 3d 20 6e |;.  q->m|oves = n|
|000013c0| 65 77 5f 6d 6f 76 65 3b | 0d 20 20 69 66 20 28 64 |ew_move;|.  if (d|
|000013d0| 65 70 74 68 20 3d 3d 20 | 72 2d 3e 6d 61 78 5f 64 |epth == |r->max_d|
|000013e0| 65 70 74 68 29 0d 20 20 | 20 20 3c 3c 44 6f 75 62 |epth).  |  <<Doub|
|000013f0| 6c 65 20 74 68 65 20 73 | 69 7a 65 20 6f 66 20 74 |le the s|ize of t|
|00001400| 68 65 20 5b 5b 64 65 70 | 74 68 73 5d 5d 20 61 72 |he [[dep|ths]] ar|
|00001410| 72 61 79 3e 3e 0d 20 20 | 6e 65 77 2d 3e 6e 65 78 |ray>>.  |new->nex|
|00001420| 74 20 3d 20 72 2d 3e 64 | 65 70 74 68 73 5b 64 65 |t = r->d|epths[de|
|00001430| 70 74 68 5d 3b 0d 20 20 | 72 2d 3e 64 65 70 74 68 |pth];.  |r->depth|
|00001440| 73 5b 64 65 70 74 68 5d | 20 3d 20 6e 65 77 3b 0d |s[depth]| = new;.|
|00001450| 7d 0d 3c 3c 44 6f 75 62 | 6c 65 20 74 68 65 20 73 |}.<<Doub|le the s|
|00001460| 69 7a 65 20 6f 66 20 74 | 68 65 20 5b 5b 64 65 70 |ize of t|he [[dep|
|00001470| 74 68 73 5d 5d 20 61 72 | 72 61 79 3e 3e 3d 0d 7b |ths]] ar|ray>>=.{|
|00001480| 0d 20 20 69 6e 74 20 69 | 3b 0d 20 20 47 6f 74 6f |.  int i|;.  Goto|
|00001490| 5f 4e 6f 64 65 20 2a 2a | 6e 65 77 5f 64 65 70 74 |_Node **|new_dept|
|000014a0| 68 73 20 3d 20 28 47 6f | 74 6f 5f 4e 6f 64 65 20 |hs = (Go|to_Node |
|000014b0| 2a 2a 29 20 63 61 6c 6c | 6f 63 28 32 2a 64 65 70 |**) call|oc(2*dep|
|000014c0| 74 68 2c 20 73 69 7a 65 | 6f 66 28 47 6f 74 6f 5f |th, size|of(Goto_|
|000014d0| 4e 6f 64 65 20 2a 29 29 | 3b 0d 20 20 72 2d 3e 6d |Node *))|;.  r->m|
|000014e0| 61 78 5f 64 65 70 74 68 | 20 3d 20 32 20 2a 20 64 |ax_depth| = 2 * d|
|000014f0| 65 70 74 68 3b 0d 20 20 | 66 6f 72 20 28 69 3d 30 |epth;.  |for (i=0|
|00001500| 3b 20 69 3c 64 65 70 74 | 68 3b 20 69 2b 2b 29 0d |; i<dept|h; i++).|
|00001510| 20 20 20 20 6e 65 77 5f | 64 65 70 74 68 73 5b 69 |    new_|depths[i|
|00001520| 5d 20 3d 20 72 2d 3e 64 | 65 70 74 68 73 5b 69 5d |] = r->d|epths[i]|
|00001530| 3b 0d 20 20 66 72 65 65 | 28 72 2d 3e 64 65 70 74 |;.  free|(r->dept|
|00001540| 68 73 29 3b 0d 20 20 72 | 2d 3e 64 65 70 74 68 73 |hs);.  r|->depths|
|00001550| 20 3d 20 6e 65 77 5f 64 | 65 70 74 68 73 3b 0d 7d | = new_d|epths;.}|
|00001560| 0d 3c 3c 53 65 74 20 5b | 5b 71 2d 3e 6f 75 74 70 |.<<Set [|[q->outp|
|00001570| 75 74 5d 5d 20 74 6f 20 | 5b 5b 69 64 5d 5d 20 28 |ut]] to |[[id]] (|
|00001580| 69 66 20 6e 6f 74 20 61 | 6c 72 65 61 64 79 20 70 |if not a|lready p|
|00001590| 72 65 73 65 6e 74 29 3e | 3e 3d 0d 69 66 20 28 21 |resent)>|>=.if (!|
|000015a0| 71 2d 3e 6f 75 74 70 75 | 74 29 20 7b 0d 20 20 63 |q->outpu|t) {.  c|
|000015b0| 68 61 72 20 2a 63 6f 70 | 79 20 3d 20 6d 61 6c 6c |har *cop|y = mall|
|000015c0| 6f 63 28 73 74 72 6c 65 | 6e 28 69 64 29 20 2b 20 |oc(strle|n(id) + |
|000015d0| 31 29 3b 0d 20 20 73 74 | 72 63 70 79 28 63 6f 70 |1);.  st|rcpy(cop|
|000015e0| 79 2c 20 69 64 29 3b 0d | 20 20 71 2d 3e 6f 75 74 |y, id);.|  q->out|
|000015f0| 70 75 74 20 3d 20 28 4e | 61 6d 65 5f 4e 6f 64 65 |put = (N|ame_Node|
|00001600| 20 2a 29 20 6d 61 6c 6c | 6f 63 28 73 69 7a 65 6f | *) mall|oc(sizeo|
|00001610| 66 28 4e 61 6d 65 5f 4e | 6f 64 65 29 29 3b 0d 20 |f(Name_N|ode));. |
|00001620| 20 71 2d 3e 6f 75 74 70 | 75 74 2d 3e 6e 65 78 74 | q->outp|ut->next|
|00001630| 20 3d 20 4e 55 4c 4c 3b | 0d 20 20 71 2d 3e 6f 75 | = NULL;|.  q->ou|
|00001640| 74 70 75 74 2d 3e 6e 61 | 6d 65 20 3d 20 63 6f 70 |tput->na|me = cop|
|00001650| 79 3b 0d 7d 0d 40 0d 0d | 25 5c 6e 65 77 70 61 67 |y;.}.@..|%\newpag|
|00001660| 65 0d 5c 70 61 72 61 67 | 72 61 70 68 7b 42 75 69 |e.\parag|raph{Bui|
|00001670| 6c 64 69 6e 67 20 74 68 | 65 20 46 61 69 6c 75 72 |lding th|e Failur|
|00001680| 65 20 46 75 6e 63 74 69 | 6f 6e 73 7d 0d 0d 41 66 |e Functi|ons}..Af|
|00001690| 74 65 72 20 61 6c 6c 20 | 74 68 65 20 73 74 72 69 |ter all |the stri|
|000016a0| 6e 67 73 20 68 61 76 65 | 20 62 65 65 6e 20 61 64 |ngs have| been ad|
|000016b0| 64 65 64 20 74 6f 20 74 | 68 65 20 67 6f 74 6f 20 |ded to t|he goto |
|000016c0| 74 61 62 6c 65 2c 20 77 | 65 20 63 61 6e 0d 63 6f |table, w|e can.co|
|000016d0| 6e 73 74 72 75 63 74 20 | 74 68 65 20 66 61 69 6c |nstruct |the fail|
|000016e0| 75 72 65 20 66 75 6e 63 | 74 69 6f 6e 73 2e 20 20 |ure func|tions.  |
|000016f0| 49 74 27 73 20 67 6f 69 | 6e 67 20 74 6f 20 62 65 |It's goi|ng to be|
|00001700| 20 68 61 72 64 20 74 6f | 20 65 78 70 6c 61 69 6e | hard to| explain|
|00001710| 0d 74 68 69 73 20 6f 6e | 65 2e 0d 3c 3c 46 75 6e |.this on|e..<<Fun|
|00001720| 63 74 69 6f 6e 20 64 65 | 66 69 6e 69 74 69 6f 6e |ction de|finition|
|00001730| 73 3e 3e 3d 0d 76 6f 69 | 64 20 73 74 6f 70 5f 61 |s>>=.voi|d stop_a|
|00001740| 64 64 69 6e 67 28 52 65 | 63 6f 67 6e 69 7a 65 72 |dding(Re|cognizer|
|00001750| 20 72 29 0d 7b 0d 20 20 | 69 6e 74 20 64 65 70 74 | r).{.  |int dept|
|00001760| 68 3b 0d 20 20 66 6f 72 | 20 28 64 65 70 74 68 3d |h;.  for| (depth=|
|00001770| 31 3b 20 64 65 70 74 68 | 3c 72 2d 3e 6d 61 78 5f |1; depth|<r->max_|
|00001780| 64 65 70 74 68 3b 20 64 | 65 70 74 68 2b 2b 29 20 |depth; d|epth++) |
|00001790| 7b 0d 20 20 20 20 47 6f | 74 6f 5f 4e 6f 64 65 20 |{.    Go|to_Node |
|000017a0| 2a 67 20 3d 20 72 2d 3e | 64 65 70 74 68 73 5b 64 |*g = r->|depths[d|
|000017b0| 65 70 74 68 5d 3b 0d 20 | 20 20 20 77 68 69 6c 65 |epth];. |   while|
|000017c0| 20 28 67 29 20 7b 0d 20 | 20 20 20 20 20 4d 6f 76 | (g) {. |     Mov|
|000017d0| 65 5f 4e 6f 64 65 20 2a | 6d 20 3d 20 67 2d 3e 6d |e_Node *|m = g->m|
|000017e0| 6f 76 65 73 3b 0d 20 20 | 20 20 20 20 77 68 69 6c |oves;.  |    whil|
|000017f0| 65 20 28 6d 29 20 7b 0d | 20 20 20 20 20 20 20 20 |e (m) {.|        |
|00001800| 63 68 61 72 20 61 20 3d | 20 6d 2d 3e 63 3b 0d 20 |char a =| m->c;. |
|00001810| 20 20 20 20 20 20 20 47 | 6f 74 6f 5f 4e 6f 64 65 |       G|oto_Node|
|00001820| 20 2a 73 20 3d 20 6d 2d | 3e 73 74 61 74 65 3b 0d | *s = m-|>state;.|
|00001830| 20 20 20 20 20 20 20 20 | 47 6f 74 6f 5f 4e 6f 64 |        |Goto_Nod|
|00001840| 65 20 2a 73 74 61 74 65 | 20 3d 20 67 2d 3e 66 61 |e *state| = g->fa|
|00001850| 69 6c 3b 0d 20 20 20 20 | 20 20 20 20 77 68 69 6c |il;.    |    whil|
|00001860| 65 20 28 73 74 61 74 65 | 20 26 26 20 21 67 6f 74 |e (state| && !got|
|00001870| 6f 5f 6c 6f 6f 6b 75 70 | 28 61 2c 20 73 74 61 74 |o_lookup|(a, stat|
|00001880| 65 29 29 0d 20 20 20 20 | 20 20 20 20 20 20 73 74 |e)).    |      st|
|00001890| 61 74 65 20 3d 20 73 74 | 61 74 65 2d 3e 66 61 69 |ate = st|ate->fai|
|000018a0| 6c 3b 0d 20 20 20 20 20 | 20 20 20 69 66 20 28 73 |l;.     |   if (s|
|000018b0| 74 61 74 65 29 0d 20 20 | 20 20 20 20 20 20 20 20 |tate).  |        |
|000018c0| 73 2d 3e 66 61 69 6c 20 | 3d 20 67 6f 74 6f 5f 6c |s->fail |= goto_l|
|000018d0| 6f 6f 6b 75 70 28 61 2c | 20 73 74 61 74 65 29 3b |ookup(a,| state);|
|000018e0| 0d 20 20 20 20 20 20 20 | 20 65 6c 73 65 0d 20 20 |.       | else.  |
|000018f0| 20 20 20 20 20 20 20 20 | 73 2d 3e 66 61 69 6c 20 |        |s->fail |
|00001900| 3d 20 72 2d 3e 72 6f 6f | 74 5b 61 5d 3b 0d 20 20 |= r->roo|t[a];.  |
|00001910| 20 20 20 20 20 20 69 66 | 20 28 73 2d 3e 66 61 69 |      if| (s->fai|
|00001920| 6c 29 20 7b 0d 20 20 20 | 20 20 20 20 20 20 20 4e |l) {.   |       N|
|00001930| 61 6d 65 5f 4e 6f 64 65 | 20 2a 70 20 3d 20 73 2d |ame_Node| *p = s-|
|00001940| 3e 66 61 69 6c 2d 3e 6f | 75 74 70 75 74 3b 0d 20 |>fail->o|utput;. |
|00001950| 20 20 20 20 20 20 20 20 | 20 77 68 69 6c 65 20 28 |        | while (|
|00001960| 70 29 20 7b 0d 20 20 20 | 20 20 20 20 20 20 20 20 |p) {.   |        |
|00001970| 20 4e 61 6d 65 5f 4e 6f | 64 65 20 2a 71 20 3d 20 | Name_No|de *q = |
|00001980| 28 4e 61 6d 65 5f 4e 6f | 64 65 20 2a 29 20 6d 61 |(Name_No|de *) ma|
|00001990| 6c 6c 6f 63 28 73 69 7a | 65 6f 66 28 4e 61 6d 65 |lloc(siz|eof(Name|
|000019a0| 5f 4e 6f 64 65 29 29 3b | 0d 20 20 20 20 20 20 20 |_Node));|.       |
|000019b0| 20 20 20 20 20 71 2d 3e | 6e 61 6d 65 20 3d 20 70 |     q->|name = p|
|000019c0| 2d 3e 6e 61 6d 65 3b 20 | 2f 2a 20 64 65 70 65 6e |->name; |/* depen|
|000019d0| 64 69 6e 67 20 6f 6e 20 | 6d 65 6d 6f 72 79 20 64 |ding on |memory d|
|000019e0| 65 61 6c 6c 6f 63 61 74 | 69 6f 6e 20 0d 20 20 20 |eallocat|ion .   |
|000019f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |        |        |
|00001a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 73 |        |       s|
|00001a10| 74 72 61 74 65 67 79 2c | 20 77 65 20 6d 61 79 20 |trategy,| we may |
|00001a20| 6e 65 65 64 20 74 6f 20 | 63 6f 70 79 20 74 68 69 |need to |copy thi|
|00001a30| 73 20 2a 2f 0d 20 20 20 | 20 20 20 20 20 20 20 20 |s */.   |        |
|00001a40| 20 71 2d 3e 6e 65 78 74 | 20 3d 20 73 2d 3e 6f 75 | q->next| = s->ou|
|00001a50| 74 70 75 74 3b 0d 20 20 | 20 20 20 20 20 20 20 20 |tput;.  |        |
|00001a60| 20 20 73 2d 3e 6f 75 74 | 70 75 74 20 3d 20 71 3b |  s->out|put = q;|
|00001a70| 0d 20 20 20 20 20 20 20 | 20 20 20 20 20 70 20 3d |.       |     p =|
|00001a80| 20 70 2d 3e 6e 65 78 74 | 3b 0d 20 20 20 20 20 20 | p->next|;.      |
|00001a90| 20 20 20 20 7d 0d 20 20 | 20 20 20 20 20 20 7d 0d |    }.  |      }.|
|00001aa0| 20 20 20 20 20 20 20 20 | 6d 20 3d 20 6d 2d 3e 6e |        |m = m->n|
|00001ab0| 65 78 74 3b 0d 20 20 20 | 20 20 20 7d 0d 20 20 20 |ext;.   |   }.   |
|00001ac0| 20 20 20 67 20 3d 20 67 | 2d 3e 6e 65 78 74 3b 0d |   g = g|->next;.|
|00001ad0| 20 20 20 20 7d 0d 20 20 | 7d 0d 7d 0d 40 20 25 64 |    }.  |}.}.@ %d|
|00001ae0| 65 66 20 73 74 6f 70 5f | 61 64 64 69 6e 67 0d 40 |ef stop_|adding.@|
|00001af0| 0d 0d 5c 73 75 62 73 75 | 62 73 65 63 74 69 6f 6e |..\subsu|bsection|
|00001b00| 7b 55 73 69 6e 67 20 74 | 68 65 20 41 75 74 6f 6d |{Using t|he Autom|
|00001b10| 61 74 61 7d 0d 0d 3c 3c | 46 75 6e 63 74 69 6f 6e |ata}..<<|Function|
|00001b20| 20 64 65 66 69 6e 69 74 | 69 6f 6e 73 3e 3e 3d 0d | definit|ions>>=.|
|00001b30| 76 6f 69 64 20 73 65 61 | 72 63 68 5f 66 6f 72 5f |void sea|rch_for_|
|00001b40| 69 64 65 6e 74 28 52 65 | 63 6f 67 6e 69 7a 65 72 |ident(Re|cognizer|
|00001b50| 20 72 2c 20 63 68 61 72 | 20 2a 69 6e 70 75 74 2c | r, char| *input,|
|00001b60| 20 43 61 6c 6c 62 61 63 | 6b 20 66 2c 20 76 6f 69 | Callbac|k f, voi|
|00001b70| 64 20 2a 63 6c 6f 73 75 | 72 65 29 0d 7b 0d 20 20 |d *closu|re).{.  |
|00001b80| 47 6f 74 6f 5f 4e 6f 64 | 65 20 2a 73 74 61 74 65 |Goto_Nod|e *state|
|00001b90| 20 3d 20 4e 55 4c 4c 3b | 0d 20 20 63 68 61 72 20 | = NULL;|.  char |
|00001ba0| 2a 63 75 72 72 65 6e 74 | 20 3d 20 69 6e 70 75 74 |*current| = input|
|00001bb0| 3b 0d 20 20 63 68 61 72 | 20 63 20 3d 20 2a 63 75 |;.  char| c = *cu|
|00001bc0| 72 72 65 6e 74 2b 2b 3b | 0d 20 20 77 68 69 6c 65 |rrent++;|.  while|
|00001bd0| 20 28 63 29 20 7b 0d 20 | 20 20 20 3c 3c 47 6f 74 | (c) {. |   <<Got|
|00001be0| 6f 20 74 68 65 20 6e 65 | 78 74 20 73 74 61 74 65 |o the ne|xt state|
|00001bf0| 3e 3e 0d 20 20 20 20 3c | 3c 50 65 72 66 6f 72 6d |>>.    <|<Perform|
|00001c00| 20 74 68 65 20 63 61 6c | 6c 62 61 63 6b 20 66 6f | the cal|lback fo|
|00001c10| 72 20 61 6e 79 20 6f 75 | 74 70 75 74 73 3e 3e 0d |r any ou|tputs>>.|
|00001c20| 20 20 20 20 63 20 3d 20 | 2a 63 75 72 72 65 6e 74 |    c = |*current|
|00001c30| 2b 2b 3b 0d 20 20 7d 0d | 7d 0d 40 20 25 64 65 66 |++;.  }.|}.@ %def|
|00001c40| 20 73 65 61 72 63 68 5f | 66 6f 72 5f 69 64 65 6e | search_|for_iden|
|00001c50| 74 0d 40 0d 54 68 69 73 | 20 69 73 20 61 6c 6c 20 |t.@.This| is all |
|00001c60| 63 6f 6d 70 6c 69 63 61 | 74 65 64 20 62 79 20 6d |complica|ted by m|
|00001c70| 79 20 75 73 65 20 6f 66 | 20 5b 5b 4e 55 4c 4c 5d |y use of| [[NULL]|
|00001c80| 5d 20 74 6f 20 69 6e 64 | 69 63 61 74 65 20 74 68 |] to ind|icate th|
|00001c90| 65 0d 69 6e 69 74 69 61 | 6c 20 73 74 61 74 65 2e |e.initia|l state.|
|00001ca0| 20 48 6f 77 65 76 65 72 | 2c 20 77 65 20 67 65 74 | However|, we get|
|00001cb0| 20 61 20 6e 69 63 65 20 | 73 70 65 65 64 75 70 20 | a nice |speedup |
|00001cc0| 62 79 20 75 73 69 6e 67 | 20 74 68 65 20 5b 5b 72 |by using| the [[r|
|00001cd0| 6f 6f 74 5d 5d 0d 61 72 | 72 61 79 20 69 6e 73 74 |oot]].ar|ray inst|
|00001ce0| 65 61 64 20 6f 66 20 77 | 61 6c 6b 69 6e 67 20 64 |ead of w|alking d|
|00001cf0| 6f 77 6e 20 74 68 65 20 | 6d 6f 76 65 20 6c 69 73 |own the |move lis|
|00001d00| 74 20 66 6f 72 20 65 76 | 65 72 79 20 63 68 61 72 |t for ev|ery char|
|00001d10| 61 63 74 65 72 2e 0d 3c | 3c 47 6f 74 6f 20 74 68 |acter..<|<Goto th|
|00001d20| 65 20 6e 65 78 74 20 73 | 74 61 74 65 3e 3e 3d 0d |e next s|tate>>=.|
|00001d30| 7b 0d 20 20 77 68 69 6c | 65 20 28 73 74 61 74 65 |{.  whil|e (state|
|00001d40| 20 26 26 20 21 67 6f 74 | 6f 5f 6c 6f 6f 6b 75 70 | && !got|o_lookup|
|00001d50| 28 63 2c 20 73 74 61 74 | 65 29 29 0d 20 20 20 20 |(c, stat|e)).    |
|00001d60| 73 74 61 74 65 20 3d 20 | 73 74 61 74 65 2d 3e 66 |state = |state->f|
|00001d70| 61 69 6c 3b 0d 20 20 73 | 74 61 74 65 20 3d 20 73 |ail;.  s|tate = s|
|00001d80| 74 61 74 65 20 3f 20 67 | 6f 74 6f 5f 6c 6f 6f 6b |tate ? g|oto_look|
|00001d90| 75 70 28 63 2c 20 73 74 | 61 74 65 29 20 3a 20 72 |up(c, st|ate) : r|
|00001da0| 2d 3e 72 6f 6f 74 5b 63 | 5d 3b 0d 7d 0d 40 0d 0d |->root[c|];.}.@..|
|00001db0| 57 65 20 77 61 6c 6b 20 | 64 6f 77 6e 20 74 68 65 |We walk |down the|
|00001dc0| 20 6f 75 74 70 75 74 20 | 6c 69 73 74 2c 20 63 61 | output |list, ca|
|00001dd0| 6c 6c 69 6e 67 20 5b 5b | 66 5d 5d 20 77 69 74 68 |lling [[|f]] with|
|00001de0| 20 65 61 63 68 20 6e 61 | 6d 65 20 74 68 61 74 20 | each na|me that |
|00001df0| 69 73 0d 6e 6f 74 20 72 | 65 6a 65 63 74 65 64 20 |is.not r|ejected |
|00001e00| 28 73 65 65 20 74 68 65 | 20 6e 65 78 74 20 73 65 |(see the| next se|
|00001e10| 63 74 69 6f 6e 29 2e 0d | 3c 3c 50 65 72 66 6f 72 |ction)..|<<Perfor|
|00001e20| 6d 20 74 68 65 20 63 61 | 6c 6c 62 61 63 6b 20 66 |m the ca|llback f|
|00001e30| 6f 72 20 61 6e 79 20 6f | 75 74 70 75 74 73 3e 3e |or any o|utputs>>|
|00001e40| 3d 0d 7b 0d 20 20 69 66 | 20 28 73 74 61 74 65 29 |=.{.  if| (state)|
|00001e50| 20 7b 0d 20 20 20 20 4e | 61 6d 65 5f 4e 6f 64 65 | {.    N|ame_Node|
|00001e60| 20 2a 70 20 3d 20 73 74 | 61 74 65 2d 3e 6f 75 74 | *p = st|ate->out|
|00001e70| 70 75 74 3b 0d 20 20 20 | 20 77 68 69 6c 65 20 28 |put;.   | while (|
|00001e80| 70 29 20 7b 0d 20 20 20 | 20 20 20 69 66 20 28 21 |p) {.   |   if (!|
|00001e90| 72 65 6a 65 63 74 5f 6d | 61 74 63 68 28 72 2c 20 |reject_m|atch(r, |
|00001ea0| 70 2d 3e 6e 61 6d 65 2c | 20 69 6e 70 75 74 2c 20 |p->name,| input, |
|00001eb0| 63 75 72 72 65 6e 74 29 | 29 0d 20 20 20 20 20 20 |current)|).      |
|00001ec0| 20 20 66 28 63 6c 6f 73 | 75 72 65 2c 20 70 2d 3e |  f(clos|ure, p->|
|00001ed0| 6e 61 6d 65 2c 20 63 75 | 72 72 65 6e 74 20 2d 20 |name, cu|rrent - |
|00001ee0| 73 74 72 6c 65 6e 28 70 | 2d 3e 6e 61 6d 65 29 29 |strlen(p|->name))|
|00001ef0| 3b 0d 20 20 20 20 20 20 | 70 20 3d 20 70 2d 3e 6e |;.      |p = p->n|
|00001f00| 65 78 74 3b 0d 20 20 20 | 20 7d 0d 20 20 7d 0d 7d |ext;.   | }.  }.}|
|00001f10| 0d 40 0d 0d 25 20 5c 6e | 65 77 70 61 67 65 0d 5c |.@..% \n|ewpage.\|
|00001f20| 70 61 72 61 67 72 61 70 | 68 7b 52 65 6a 65 63 74 |paragrap|h{Reject|
|00001f30| 69 6e 67 20 4d 61 74 63 | 68 65 73 7d 0d 0d 41 20 |ing Matc|hes}..A |
|00001f40| 70 72 6f 62 6c 65 6d 20 | 77 69 74 68 20 73 69 6d |problem |with sim|
|00001f50| 70 6c 65 20 73 75 62 73 | 74 72 69 6e 67 20 6d 61 |ple subs|tring ma|
|00001f60| 74 63 68 69 6e 67 20 69 | 73 20 74 68 61 74 20 74 |tching i|s that t|
|00001f70| 68 65 20 73 74 72 69 6e | 67 20 60 60 68 65 27 27 |he strin|g ``he''|
|00001f80| 0d 77 6f 75 6c 64 20 6d | 61 74 63 68 20 6c 6f 6e |.would m|atch lon|
|00001f90| 67 65 72 20 73 74 72 69 | 6e 67 73 20 6c 69 6b 65 |ger stri|ngs like|
|00001fa0| 20 60 60 73 68 65 27 27 | 20 61 6e 64 20 60 60 68 | ``she''| and ``h|
|00001fb0| 65 72 2e 27 27 20 4e 6f | 72 6d 61 6e 20 52 61 6d |er.'' No|rman Ram|
|00001fc0| 73 65 79 0d 73 75 67 67 | 65 73 74 65 64 20 65 78 |sey.sugg|ested ex|
|00001fd0| 61 6d 69 6e 69 6e 67 20 | 74 68 65 20 63 68 61 72 |amining |the char|
|00001fe0| 61 63 74 65 72 73 20 6f | 63 63 75 72 69 6e 67 20 |acters o|ccuring |
|00001ff0| 69 6d 6d 65 64 69 61 74 | 65 6c 79 20 62 65 66 6f |immediat|ely befo|
|00002000| 72 65 20 61 6e 64 0d 61 | 66 74 65 72 20 61 20 6d |re and.a|fter a m|
|00002010| 61 74 63 68 20 61 6e 64 | 20 72 65 6a 65 63 74 69 |atch and| rejecti|
|00002020| 6e 67 20 74 68 65 20 6d | 61 74 63 68 20 69 66 20 |ng the m|atch if |
|00002030| 69 74 20 61 70 70 65 61 | 72 73 20 74 6f 20 62 65 |it appea|rs to be|
|00002040| 20 70 61 72 74 20 6f 66 | 20 61 0d 6c 6f 6e 67 65 | part of| a.longe|
|00002050| 72 20 74 6f 6b 65 6e 2e | 20 4f 66 20 63 6f 75 72 |r token.| Of cour|
|00002060| 73 65 2c 20 74 68 65 20 | 63 6f 6e 63 65 70 74 20 |se, the |concept |
|00002070| 6f 66 20 7b 5c 73 6c 20 | 74 6f 6b 65 6e 5c 2f 7d |of {\sl |token\/}|
|00002080| 20 69 73 0d 6c 61 6e 67 | 75 61 67 65 2d 64 65 70 | is.lang|uage-dep|
|00002090| 65 6e 64 65 6e 74 2c 20 | 73 6f 20 77 65 20 6d 61 |endent, |so we ma|
|000020a0| 79 20 62 65 20 6f 63 63 | 61 73 69 6f 6e 61 6c 6c |y be occ|asionall|
|000020b0| 79 20 6d 69 73 74 61 6b | 65 6e 2e 0d 46 6f 72 20 |y mistak|en..For |
|000020c0| 74 68 65 20 70 72 65 73 | 65 6e 74 2c 20 77 65 27 |the pres|ent, we'|
|000020d0| 6c 6c 20 63 6f 6e 73 69 | 64 65 72 20 74 68 65 20 |ll consi|der the |
|000020e0| 6d 65 63 68 61 6e 69 73 | 6d 20 61 6e 20 65 78 70 |mechanis|m an exp|
|000020f0| 65 72 69 6d 65 6e 74 2e | 0d 0d 3c 3c 46 75 6e 63 |eriment.|..<<Func|
|00002100| 74 69 6f 6e 20 64 65 66 | 69 6e 69 74 69 6f 6e 73 |tion def|initions|
|00002110| 3e 3e 3d 0d 69 6e 74 20 | 72 65 6a 65 63 74 5f 6d |>>=.int |reject_m|
|00002120| 61 74 63 68 28 52 65 63 | 6f 67 6e 69 7a 65 72 20 |atch(Rec|ognizer |
|00002130| 72 2c 20 63 68 61 72 20 | 2a 69 64 2c 20 63 68 61 |r, char |*id, cha|
|00002140| 72 20 2a 69 6e 70 75 74 | 2c 20 63 68 61 72 20 2a |r *input|, char *|
|00002150| 63 75 72 72 65 6e 74 29 | 0d 7b 0d 20 20 69 6e 74 |current)|.{.  int|
|00002160| 20 6c 65 6e 20 3d 20 73 | 74 72 6c 65 6e 28 69 64 | len = s|trlen(id|
|00002170| 29 3b 0d 20 20 63 68 61 | 72 20 66 69 72 73 74 20 |);.  cha|r first |
|00002180| 3d 20 69 64 5b 30 5d 3b | 0d 20 20 63 68 61 72 20 |= id[0];|.  char |
|00002190| 6c 61 73 74 20 3d 20 69 | 64 5b 6c 65 6e 20 2d 20 |last = i|d[len - |
|000021a0| 31 5d 3b 0d 20 20 63 68 | 61 72 20 6e 65 78 74 20 |1];.  ch|ar next |
|000021b0| 3d 20 2a 63 75 72 72 65 | 6e 74 3b 0d 20 20 63 68 |= *curre|nt;.  ch|
|000021c0| 61 72 20 70 72 65 76 20 | 3d 20 27 5c 30 27 3b 0d |ar prev |= '\0';.|
|000021d0| 20 20 63 75 72 72 65 6e | 74 20 3d 20 63 75 72 72 |  curren|t = curr|
|000021e0| 65 6e 74 20 2d 20 6c 65 | 6e 20 2d 20 31 3b 0d 20 |ent - le|n - 1;. |
|000021f0| 20 69 66 20 28 69 6e 70 | 75 74 20 3c 3d 20 63 75 | if (inp|ut <= cu|
|00002200| 72 72 65 6e 74 29 0d 20 | 20 20 20 70 72 65 76 20 |rrent). |   prev |
|00002210| 3d 20 2a 63 75 72 72 65 | 6e 74 3b 0d 20 20 69 66 |= *curre|nt;.  if|
|00002220| 20 28 73 74 72 63 68 72 | 28 72 2d 3e 61 6c 70 68 | (strchr|(r->alph|
|00002230| 61 73 2c 20 66 69 72 73 | 74 29 20 26 26 20 73 74 |as, firs|t) && st|
|00002240| 72 63 68 72 28 72 2d 3e | 61 6c 70 68 61 73 2c 20 |rchr(r->|alphas, |
|00002250| 70 72 65 76 29 29 20 72 | 65 74 75 72 6e 20 31 3b |prev)) r|eturn 1;|
|00002260| 0d 20 20 69 66 20 28 73 | 74 72 63 68 72 28 72 2d |.  if (s|trchr(r-|
|00002270| 3e 61 6c 70 68 61 73 2c | 20 6c 61 73 74 20 29 20 |>alphas,| last ) |
|00002280| 26 26 20 73 74 72 63 68 | 72 28 72 2d 3e 61 6c 70 |&& strch|r(r->alp|
|00002290| 68 61 73 2c 20 6e 65 78 | 74 29 29 20 72 65 74 75 |has, nex|t)) retu|
|000022a0| 72 6e 20 31 3b 0d 20 20 | 69 66 20 28 73 74 72 63 |rn 1;.  |if (strc|
|000022b0| 68 72 28 72 2d 3e 73 79 | 6d 73 2c 20 20 20 66 69 |hr(r->sy|ms,   fi|
|000022c0| 72 73 74 29 20 26 26 20 | 73 74 72 63 68 72 28 72 |rst) && |strchr(r|
|000022d0| 2d 3e 73 79 6d 73 2c 20 | 20 20 70 72 65 76 29 29 |->syms, |  prev))|
|000022e0| 20 72 65 74 75 72 6e 20 | 31 3b 0d 20 20 69 66 20 | return |1;.  if |
|000022f0| 28 73 74 72 63 68 72 28 | 72 2d 3e 73 79 6d 73 2c |(strchr(|r->syms,|
|00002300| 20 20 20 6c 61 73 74 20 | 29 20 26 26 20 73 74 72 |   last |) && str|
|00002310| 63 68 72 28 72 2d 3e 73 | 79 6d 73 2c 20 20 20 6e |chr(r->s|yms,   n|
|00002320| 65 78 74 29 29 20 72 65 | 74 75 72 6e 20 31 3b 0d |ext)) re|turn 1;.|
|00002330| 20 20 72 65 74 75 72 6e | 20 30 3b 0d 7d 0d 40 20 |  return| 0;.}.@ |
|00002340| 25 64 65 66 20 72 65 6a | 65 63 74 5f 6d 61 74 63 |%def rej|ect_matc|
|00002350| 68 0d 57 65 20 6e 65 65 | 64 20 61 20 70 72 6f 74 |h.We nee|d a prot|
|00002360| 6f 74 79 70 65 20 66 6f | 72 20 5b 5b 72 65 6a 65 |otype fo|r [[reje|
|00002370| 63 74 5f 6d 61 74 63 68 | 5d 5d 2c 20 73 69 6e 63 |ct_match|]], sinc|
|00002380| 65 20 69 74 27 73 20 72 | 65 66 65 72 65 6e 63 65 |e it's r|eference|
|00002390| 64 0d 62 65 66 6f 72 65 | 20 69 74 73 20 64 65 66 |d.before| its def|
|000023a0| 69 6e 69 74 69 6f 6e 2e | 0d 0d 3c 3c 50 72 6f 74 |inition.|..<<Prot|
|000023b0| 6f 74 79 70 65 73 3e 3e | 3d 0d 69 6e 74 20 72 65 |otypes>>|=.int re|
|000023c0| 6a 65 63 74 5f 6d 61 74 | 63 68 28 52 65 63 6f 67 |ject_mat|ch(Recog|
|000023d0| 6e 69 7a 65 72 20 72 2c | 20 63 68 61 72 20 2a 69 |nizer r,| char *i|
|000023e0| 64 2c 20 63 68 61 72 20 | 2a 69 6e 70 75 74 2c 20 |d, char |*input, |
|000023f0| 63 68 61 72 20 2a 63 75 | 72 72 65 6e 74 29 3b 0d |char *cu|rrent);.|
+--------+-------------------------+-------------------------+--------+--------+